package cn.xaut.剑指offer.m01;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer 10- I. 斐波那契数列
 */
public class demo09 {

    // 超时
    public int fib(int n) {

        if (n < 2)
            return n;
        return fib(n - 1) + fib(n - 2);
    }

    // 递归 + map
    public int fib2(int n) {
        return fib2(n, new HashMap<>());
    }

    public int fib2(int n, Map<Integer, Integer> map) {
        
        if (n < 2)
            return n;
        if (map.containsKey(n)) 
            return map.get(n);
        
        int first = fib2(n - 1, map);
        map.put(n - 1, first);
        int second = fib2(n - 2, map);
        map.put(n - 2, second);

        return (first + second) % 1000000007;
    }

    
    // 动态规划
    public int fib3(int n) {
        
        if (n < 2)
            return n;
        
        int[] res = new int[n + 1];
        res[0] = 0;
        res[1] = 1;
        for (int i = 2; i <= n; i++) 
            res[i] = (res[i - 1] + res[i - 2]) % 1000000007;
        
        return res[n];
    }
    
    
    public static void main(String[] args) {

        System.out.println(new demo09().fib(2));
        System.out.println(new demo09().fib(5));
    }
}
